อัลกอริธึมพันธุกรรม (GAs)เป็นวิธีการค้นหาเชิงสุ่มแบบทั่วถึงที่ได้รับแรงบันดาลใจจากหลักการของการวิวัฒนาการตามธรรมชาติ โดยเฉพาะแนวคิดเรื่อง "การอยู่รอดของผู้ที่แข็งแรงที่สุด" ตามทฤษฎีของดาร์วิน และการรวมพันธุกรรม
1. โครงสร้างการแทนข้อมูล
- อัลกอริธึมพันธุกรรมแบบคลาสสิก:ใช้การแทนข้อมูลแบบไบนารีหรือสายอักษรเกรย์เพื่อเข้ารหัสตัวแปรตัดสินใจ
- อัลกอริธึมพันธุกรรมแบบจำนวนจริง (RCGAs):จัดการกับเวกเตอร์จำนวนจริงโดยตรง มักมีประสิทธิภาพมากกว่าในการแก้ปัญหาการเพิ่มประสิทธิภาพแบบต่อเนื่อง
2. วงจรวิวัฒนาการ
กระบวนการวนซ้ำของการประเมิน คัดเลือก และการสืบพันธุ์ แนวคิดสำคัญหนึ่งคือความแตกต่างระหว่าง จีโนไทป์ (สายบิตที่เข้ารหัส/โครโมโซม) กับ เฟโนไทป์ (ค่าตัวแปรตัดสินใจที่ถอดรหัสแล้วในพื้นที่ปัญหาจริง)
การแปลงจากสายไบนารีไปยังค่าจริง $x \in [a, b]$ กำหนดโดย:
$$x = a + \frac{ค่าเดซิมอล \times (b - a)}{2^L - 1}$$
โดยที่ $L$ คือความยาวบิตของโครโมโซม
ช่องว่างแฮมมิง
ระวัง ช่องว่างแฮมมิงในรหัสไบนารีมาตรฐาน—สถานการณ์ที่เลขทศนิยมที่ใกล้เคียงกัน (เช่น 7 และ 8) มีรูปแบบบิตไบนารีที่ต่างกันอย่างสิ้นเชิง (
0111เปรียบเทียบกับ1000) ทำให้เกิดความยากลำบากสำหรับอัลกอริธึมพันธุกรรมในการค้นหาแบบท้องถิ่น
การนำไปใช้งานด้วยภาษาไพทอน: การถอดรหัสจากไบนารีเป็นจำนวนจริง
คำถามที่ 1
ทำไมการเข้ารหัสแบบเกรย์จึงได้รับความนิยมมากกว่าการเข้ารหัสไบนารีทั่วไปในอัลกอริธึมพันธุกรรม?
คำถามที่ 2
หากอัตราการกลายพันธุ์ (p) ตั้งไว้สูงเกินไป (เช่น p = 0.5) ผลลัพธ์ที่อาจเกิดขึ้นคืออะไร?
กรณีศึกษา: การเพิ่มประสิทธิภาพชิ้นส่วนสะพาน
อ่านสถานการณ์ด้านล่างแล้วตอบคำถาม
คุณกำลังเพิ่มประสิทธิภาพการออกแบบชิ้นส่วนสะพาน ซึ่งตัวแปรตัดสินใจคือ "ความหนาของวัสดุ"
- ความหนามีค่าตั้งแต่0.0 มม.ถึง10.23 มม..
- คุณใช้อัลกอริธึมพันธุกรรมแบบคลาสสิกที่มี10 บิตการแทนข้อมูลสายไบนารี
คำถาม
1. ถ้าบุคคลหนึ่งมีโครโมโซม
0000000000 ความหนาที่ถอดรหัสได้คือเท่าไร?คำตอบ: 0.0 มม.
สายไบนารี
สายไบนารี
0000000000 เท่ากับ 0 ในระบบเลขฐานสิบ ใช้สูตร $x = a + \frac{ค่าเดซิมอล \times (b-a)}{2^L - 1}$ เราได้ $0.0 + \frac{0 \times (10.23 - 0.0)}{1023} = 0.0$.
คำถาม
2. คำนวณความแม่นยำในการค้นหา (การเปลี่ยนแปลงที่เล็กที่สุดของความหนา) สำหรับการตั้งค่า 10 บิตนี้
คำตอบ: 0.01 มม.
ความแม่นยำกำหนดโดยช่วงหารด้วยค่าเดซิมอลสูงสุดที่เป็นไปได้ $\frac{10.23 - 0}{2^{10} - 1} = \frac{10.23}{1023} = 0.01มม.$
ความแม่นยำกำหนดโดยช่วงหารด้วยค่าเดซิมอลสูงสุดที่เป็นไปได้ $\frac{10.23 - 0}{2^{10} - 1} = \frac{10.23}{1023} = 0.01มม.$
คำถาม
3. ในการคัดเลือก บุคคล A มีค่าความเหมาะสม 10 และบุคคล B มีค่าความเหมาะสม 30 โดยใช้วิธีการคัดเลือกแบบล้อเล็ก ความน่าจะเป็นที่จะเลือก B แทน A คือเท่าไร?
คำตอบ: 75%
ค่าความเหมาะสมรวม = $10 + 30 = 40$. ความน่าจะเป็นในการเลือก B = $\frac{30}{40} = 0.75$ หรือ 75% (อัตราส่วน 3:1)
ค่าความเหมาะสมรวม = $10 + 30 = 40$. ความน่าจะเป็นในการเลือก B = $\frac{30}{40} = 0.75$ หรือ 75% (อัตราส่วน 3:1)